package 单链表;

import java.util.Vector;

public class SinglyList<T> {
    public Node<T> head;

    public SinglyList() {
        this.head = new Node<>();
    }

    public SinglyList(T[] values) {
        this(); //初始化空的头节点
        Node<T> rear = this.head;
        for (int i = 0; i < values.length; i++) {
            if (values[i] != null) {
                rear.next = new Node<>(values[i], null);
                rear = rear.next;
            }
        }
    }

    public SinglyList(SinglyList<T> singlyList) {
        this(); // 初始化空的头节点
        Node<T> p = singlyList.head.next;
        Node<T> rear = this.head;
        while (p != null) {
            rear.next = new Node<>(p.data, null);
            rear = rear.next;
            p=p.next;
        }
    }


    //打印
    public void display() {
        Node<T> node = head.next;
        while (node.next != null) {
            System.out.print(node.data + " ->");
            node = node.next;
        }
        System.out.println(node.data);
    }

    public int size() {
        int count = 0;
        if (this.head.next == null) {
            return 0;
        }
        Node<T> p = this.head.next;
        while (p != null) {
            count++;
            p = p.next;
        }
        return count;
    }

    public void remove(SinglyList<T> singlyList) {
        //删除采用双指针的思想
        Node cur = singlyList.head.next; //从第一个节点开始
        Node slow = this.head;
        Node fast = this.head.next;

        if (matched(singlyList)) {
            while (!cur.data.equals(fast.data)) {
                fast = fast.next;
                slow = slow.next;
            }
            while (fast != null && fast.data != null && cur != null && cur.data != null && cur.data.equals(fast.data)) {
                fast = fast.next;
                cur = cur.next;
            }
            slow.next = fast;
        }
    }


    public boolean matched(SinglyList<T> singlyList) {
        //判断是否匹配
        Node p = singlyList.head.next;//第一个节点开始
        Node cur = this.head.next;
        boolean flag = false;
        while (p.next != null) {
            //如果不相等就进行下一次的匹配
            if (!p.data.equals(cur.data)) {  //如果不相等cur就是继续匹配
                cur = cur.next;
                flag = false;
                continue;//继续执行下一次的
            } else if (p.data.equals(cur.data)) {
                //如果相等就继续下一次的查询
                flag = true;   //如果相等了，看下一个是不是相等的，如果不等那么就不行
                //如何避免空指针异常
                if (p.next != null && p.next.data != null && cur.data != null && !p.next.data.equals(cur.next.data)) {
                    flag = false;
                    return flag;
                }
                cur = cur.next;
                p = p.next;
            }
        }
        return true;
    }

    //        public void removeAllMatched(SinglyList<T> pattern) {
//        if (pattern == null || pattern.head.next == null) {
//            return; // 如果模式链表为空，则无需删除
//        }
//
//        Node<T> pre = this.head; // pre 指向当前检查节点的前一个节点
//        Node<T> p = this.head.next; // p 指向当前检查的节点
//
//        while (p != null) {
//            Node<T> tempP = p;
//            Node<T> tempQ = pattern.head.next;
//
//            // 检查从 p 开始的子链表是否匹配模式链表
//            while (tempQ != null && tempP != null && tempP.data.equals(tempQ.data)) {
//                tempP = tempP.next;
//                tempQ = tempQ.next;
//            }
//
//            if (tempQ == null) { // 完全匹配
//                pre.next = tempP; // 删除匹配的部分
//                p = tempP; // 继续从匹配部分之后的节点开始检查
//            } else {
//                pre = p; // 没有匹配，移动 pre 指针
//                p = p.next; // 移动 p 指针
//            }
//        }
    public void removeAllMathced(SinglyList<T> pattern) {
        Node<T> p = this.head.next;
        Node<T> pre = this.head;
        while (p != null) {
            Node<T> tp = p;
            Node<T> q = pattern.head.next;
            while (tp != null && q != null && tp.data.equals(q.data)) {
                tp = tp.next;
                q = q.next;
            }
            if (q == null) {
                //匹配成功了 完全匹配
                pre.next = tp;  //这边是删除匹配的部分
                p = tp;  //再移动p 开始进行检查
            } else {
                //不匹配
                pre = p;
                p = p.next;
            }
        }
    }

    public void removeNotEqual(T value) {
        Node<T> p = this.head;  //拿到当前第一个节点  p.next 不为空
        while (p.next != null) {
            if (!p.next.data.equals(value)) {
                p.next = p.next.next;
            } else {
                p = p.next;
            }
        }
    }

    public boolean isContains(SinglyList<T> list) {
        //判断 是否包含 list链表
        Node<T> p = this.head.next;
        Node<T> q = list.head.next;
        while (p != null) {
            if (p.data.equals(q.data)) {
                Node<T> tempP = p;
                Node<T> tempQ = q;
                while (tempP != null && tempQ != null && tempP.data.equals(tempQ.data)) {
                    tempP = tempP.next;
                    tempQ = tempQ.next;
                }
                //完全匹配成功了
                if (tempQ == null) {
                    return true;
                }
            }
            p = p.next;
        }
        return false;
    }

    public void reverse() {
        //反转单链表
        Node<T> p = this.head.next;
        Node<T> front = null;
        Node<T> next;
        while (p != null) {
            next = p.next;
            p.next = front;
            front = p;
            p = next;
        }
        //更新 head 的 next 指针为新的头节点
        this.head.next = front;
    }

    public static void main(String[] args) {
        Integer[] arr = {1, 2, 3, 2, 3, 4, 5};
        Integer[] arr2 = {2, 3, 2, 3, 4};
        SinglyList singlyList = new SinglyList<>(arr);
//        SinglyList singlyList2 = new SinglyList<>(arr2);
//        System.out.println(singlyList.isContains(singlyList2));
      SinglyList singlyList1=new SinglyList<>(singlyList);
      singlyList1.display();
    }
}
